\section{二分搜索算法}
\subsection{在排序数组中查找元素的第一个和最后一个位置}
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
\begin{Textcode}
	输入：nums = [5,7,7,8,8,10], target = 8
	输出：[3,4]
\end{Textcode}
\begin{Mind}{排序数组元素出现的第一个和最后一个位置}{}
	从头开始找到第一个$\geq target$的位置，然后找到第一个$\leq target$的位置即可。
\end{Mind}
\begin{enumerate}
	\item $left=0、right=n-1$，left更新的时候$[left,mid]$和$[mid+1,right]$，$mid = \frac{left+right}{2}$。
	\item $left=0、right=n-1$，left更新的时$[left,mid-1]$，$[mid,right]$，$mid = \frac{left+right+1}{2}$。因为mid计算过程是向下取整，如果按照$mid = \frac{left+right}{2}$更新，当$right=left+1$的时候会出现$mid = \frac{left+left+1}{2}=left$下一步更新的时候$left=mid$左边界没变化导致死循环。
\end{enumerate}
\begin{enumerate}
	\item 方法1更新的时候如果$nums[mid]<target$意味着($mid+1\geq target$)，此时$\geq target$的边界由$[mid+1,right]$覆盖，这样能做到最后得到的索引就是第一个$\geq target$的索引。
	\item 方法2更新的时候如果$nums[mid]>target$意味着$nums[mid-1]\leq target$，此时$\leq target$的边界由$[0,mid-1]$覆盖，这样能做到最后得到的索引就是第一个$> target$的索引的前一个索引。
\end{enumerate}
实现代码如\coderef{code:searchRange}。
\begin{longlisting}
	\caption{排序数组中查找第一个和最后一个元素的位置}
	\cppfile[firstline=3,lastline=33]{third_party/coding/cxx/algorithm/binary_search/src/searchRange.cc}
	\label{code:searchRange}
\end{longlisting}

\subsection{查找有序数组中最先出现的目标}
找到排序数组中第一个出现的目标的索引，如果没有找到则返回索引-1。需要注意的是可能有多个目标，算法核心是找到第一个出现的目标。比如输入nums=[2,7,7,8,8,10]，target=8。因为nums[3]=nums[4]=8，我们需要的是第一个目标，结果返回3。

\begin{Textcode}
	给定一个输入向量nums 和目标值target。找到其中第一个target的位置。
	示例 1:
	输入:
	[2,7,7,8,8,10],8
	输出:

	3
\end{Textcode}
\begin{Mind}{找到第一个出现的target位置}{}
同样是二分法，如果mid元素大于target则毫无疑问，right指针应该移动到mid的前一个(right=mid-1)。如果mid的元素==target则表示指向更大元素的right指针应该指向mid(right=mid)位置，因为如果向 mid-1 的位置移动会导致下轮搜索的时候漏掉了target。如果mid的元素<target则为了找到目标指向更小元素的left应该移动到mid的下一个位置（left=mid+1）。
\end{Mind}
\begin{itemize}
	\item nums[mid]>target：则代表更大元素的right指针一定指向mid左边(target = mid-1)。
	\item nums[mid]=target：则代表当前位置往左边依然可能存在target，如果不存在则当前位置就是最后结果，下次搜索的时候在right=mid位置开始。
	\item nums[mid]<target：则代表更小元素的left指针一定指向mid的右边(left=mid+1)。
\end{itemize}
这里需要注意的一点是计算中值如果使用$\frac{left+right}{2}$则意味着向下取整。这会导致又指针向左移动以更好地找到第一个目标。比如\figref{fig:find_first_target}中左右指针都指向8的时候（left=3,right=4）计算中的mid为3，导致指针左移以更好地找到第一个目标。如果你想找到最后一个目标则$mid = \frac{left+right+1}{2}$会更偏向于右边。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.6\textwidth]{find_first_target}
	\caption{查找排序数组中第一个目标}
	\label{fig:find_first_target}
\end{figure}
需要注意的是有时候并不一定能找到目标\figref{fig:find_first_target1}。这时候跳出循环意味着可能找到了错误的值，需要判断一下这时的值是不是目标，是的话才算找到。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.6\textwidth]{find_first_target1}
	\caption{找不到目标的情况}
	\label{fig:find_first_target1}
\end{figure}
找到有序数组中最后出现的元素和上面稍有不同。如nums=[2,7,7,8,8,10]，target=8返回结果4。和上面的做法类似：
\begin{itemize}
	\item nums[mid]>target：则代表更大元素的right指针一定指向mid左边(target = mid-1)。
	\item nums[mid]=target：则代表当前位置往右边依然可能存在target，如果不存在则当前位置就是最后结果，下次搜索的时候在left=mid位置开始。
	\item nums[mid]<target：则代表更小元素的left指针一定指向mid的右边(left=mid+1)。
\end{itemize}
和上面的说法类似，如果碰到两个相等的元素，mid的计算需要偏向于右边。所以$mid = \frac{left+right+1}{2}$。整个计算更新如\figref{fig:find_last_target}。

\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.6\textwidth]{find_last_target}
	\caption{查找排序数组中最后一个目标}
	\label{fig:find_last_target}
\end{figure}
\subsection{旋转数组中最小数字}
\begin{example}[获取旋转数组中的最小数字]
	把一个数组最开始的若干元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1.
\end{example}
\begin{Mind}{查找旋转数组中的最小值}{}
	旋转数组的两部分都是有序的,一个从大到小排列的数组旋转后导致旋转后的的部分比数组最开始的元素大,所以通过二分法查找中间元素是不是大于最开始的元素如果是则逆序肯定在中点右侧,否则在中点左侧。反复缩小查找范围最后获得结果。上下指针指向同一个元素的时候这个元素就是旋转后的最小值。
\end{Mind}
\begin{longlisting}
	\caption{旋转数组中最小数字}
	\cppfile[firstline=5,lastline=17]{third_party/coding/cxx/algorithm/common/src/findMin.cc}
	\label{code:findMin}
\end{longlisting}


\subsection{寻找两个正序数组的中位数}
\begin{Textcode}
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数（偶数个元素则为排序之后中间的两个元素的均值，奇数则直接为中间值） 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
\end{Textcode}
\begin{Mind}{寻找两个正序数组的中位数}{}
首先将两个数组使用分割线切分，如果第一个分割线左边的元素小于第二个分割线右边的元素并且第一个右边的分割线元素大于第二个分割线左边的元素则结果一定在分割线两侧。如\figref{fig:find_median_sorted_arrays}，如果两个数组都是奇数则中位数为分割线左边两个元素的最大值。如果是奇数则中位数为左边元素的最大值。划分长度的时候尽量保证分割线左边的元素总数是和右边相同的（或者右边总元素多一个）。左右总元素是可以根据两个数组的长度估算出来的。分割线的划分：
\begin{itemize}
	\item 分割线在第一个数组的第1个元素的索引为i则其应该等于前面元素个数。
	\item 分割线在第二个数组的第1个元素的索引为j则其应该等于前面元素的个数。其中($i+j = \frac{m+n+1}{2}$)
\end{itemize}
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.6\textwidth]{find_median_sorted_arrays}
	\caption{分割线划分}
	\label{fig:find_median_sorted_arrays}
\end{figure}
特殊情况处理：
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{find_median_sorted_arrays_special}
	\caption{特殊情况}
	\label{fig:find_median_sorted_arrays_special}
\end{figure}
\subsection{\href{https://leetcode.cn/problems/single-element-in-a-sorted-array/description/?envType=study-plan-v2&envId=binary-search}{有序数组中的单一元素}}
\begin{example}[有序数组中的单一元素]
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。请你找出并返回只出现一次的那个数。你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
\begin{bash}
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
\end{bash}
\end{example}
\begin{Mind}{有序数组中的单一元素}{}
首先只有奇数长度才可能出现单一元素。二分搜索的时候位置mid左右都是偶数，所以需要把mid合理的分配到左右两边。如果mid为偶数位置则其右边为偶数，如果此时mid和mid+1对应元素相等则目标在右边。否则目标在左边（包含当前元素）。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{singleNonDuplicate}
	\caption{二分实现示意图}
	\label{fig:singleNonDuplicate}
\end{figure}

解释一下为什么mid是偶数且mid+1和其对应元素相等则目标在右边。mid和mid+1对应的元素相等则判断右边是否存在目标应该是右边的元素个数-1。此时为奇数，所以结果一定在右边。\figref{fig:singleNonDuplicate}中mid=4的时候右边元素和左边相等则意味着右边的偶数个元素正好成对，所以目标一定在[left,mid]区间。
\begin{longlisting}
	\caption{有序数组中的单一元素}
	\cppfile[firstline=9,lastline=31]{third_party/coding/cxx/algorithm/binary_search/src/singleNonDuplicate.cc}
	\label{code:singleNonDuplicate}
\end{longlisting}



